Communication switching systems provide communication between sources and destinations in networks such as telephone networks and computer networks. One type of communication switching system is packet switching. In packet switching, a message from a source is split up into smaller pieces or packets. Routing information is added to each packet so that the packet can be delivered to its proper destination. The packets are output from a source to an intermediate packet switch, stored at that packet switch, then forwarded to subsequent intermediate packet switches, which also store and forward the packets, in the same manner, until the packets reach their destination.
Packet switching systems are generally of two types: (1) datagram and (2) virtual circuit systems. In datagram packet switching systems all routing information is contained in the packet in an address header. The packet can be output on any communication line. Each packet can take a different path and therefore a sequence number is required so that when the packets reach their destination they can be put back together in the correct sequence to form the original message. Datagram packet switching has drawbacks in that the packets can get out of sequence.
In a virtual circuit packet switching system, all packets are output over the same path for a certain period of time. The source and the destination agree on the path before packets are transmitted. After the path is agreed upon, routing information is setup in each intermediate packet switch which will be part of the path. The routing information in the intermediate packet switches is used in conjunction with an address header in the packets and with the input port or line that the packets come in on to route the packets.
The drawback to current virtual circuit packet switching systems is that unlike datagrams, packets must use the same path for a certain period of time. This is true even if several communication lines are provided from one intermediate packet switch to another. Using the same path allows a packet switch to route packets to an output port based on the input port or line that the packet come in on. Because delay and/or loss of packets may result when a large number of source-destination combinations use the same communication line, there is a need for the use of multiple communication lines.
Packet switches, whether they employ virtual circuit or datagram techniques, require memory for storing packets. The memory can comprise an output queue for each output port of the packet switch. When the packets are input, they can be stored in the appropriate output queue and then output in a first in first out (FIFO) manner. Techniques are also known for sharing memory between a plurality of output ports, by, for example, storing packet addresses in output queues.